<?php
/**
 *  User：LRZ
 *  Date：2020/2/11
 *  Time：16:27
 */

/**
 *  204.计数质数
 *
 *  标签：哈希表、数学
 *
 *  统计所有小于非负整数 n 的质数的数量。
 *
 *  示例:
 *      输入: 10
 *      输出: 4
 *      解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/count-primes/
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$n   = 0;
$res = countPrimes($n);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function countPrimes($n)
{
    if ($n <= 1) {
        return 0;
    }

    $isPrim = array_fill(2, $n - 2, true);
    for ($i = 2; $i * $i < $n; $i++) {
        if ($isPrim[$i]) {
            for ($j = $i * $i; $j < $n; $j += $i) {
                $isPrim[$j] = false;
            }
        }
    }

    return array_sum($isPrim);
}